Graphs are a collection of nodes connected by connections or arcs, and can have different properties. For example, an unconnected graph is a graph where not every node in the graph is reachable from every other node in the graph. To contrast, a connected graph is a graph where every node is reachable from any other node. In an unconnected graph, connections between nodes have no directional properties (e.g., the connections are bidirectional). In a directed graph, the connections between nodes have directional properties (e.g., each connection is for a one-way particular direction), but any two nodes can, in effect, emulate or mimic a bidirectional connection by having two connections, each connection being in a particular direction. A graph with a cycle is a graph in which a traversal path exists such that a node can be reached more than once on a walk of the graph. An acyclic graph is a graph in which no such traversal path exists.
A node (e.g., Node A) of a graph is considered “reachable” from another node (e.g., Node B) if a traversal path exists along the graph from Node B to Node A. A node (e.g., Node A) of a graph is considered “not reachable” from another node (e.g., Node B) if no traversal path exists along the graph from Node B to Node A.
Each node of a graph has an “in-degree” property and an “out-degree” property. A node's “in-degree” is the number of arcs (e.g., connections) leading into the node. A node's “out-degree” is the number of arcs (e.g., connections) leading from the node to other nodes.
A hierarchy graph (e.g., hierarchy) is a type of connected acyclic directed graph. A hierarchy has exactly one root node, which is a node with an in-degree of zero. All other nodes of the hierarchy graph have an in-degree of exactly one. A well-known example of a hierarchy is the directory structure of most computer file systems.
A breadth-first search receives a directed graph in which all of its nodes are reachable from some start node as an input and outputs a hierarchy graph as an output. The input directed graph can contain loops and other properties that are not allowable in a hierarchy. A breadth-first tree is the hierarchy produced from the breadth-first search. The breadth-first tree graph is a hierarchy directed graph that is connected with a start node, where all other nodes of the graph are reachable from the start node.